#include "KMP-matching.h"


int BuildNext(char const *pattern,unsigned *next){
    unsigned i = 1,j = 0;
    next[0] = 0;
    while (*(pattern + i)){
        if (*(pattern + i) == *(pattern + j)){ //match success
            next[i] = j+1;
            ++i;++j;
        }else if(j){    //
            j = next[j-1];
        }else{
            next[i] = 0;
            i++;
        }
    }
    return(0);
}

int MatchPattern(char const *text,char *pattern,int *pos){
    unsigned i = 0,j = 0;
    unsigned k = 0;

    while (*(pattern+k)) k++;
    unsigned next[k];
    BuildNext(pattern,next);

    while (*(text+i) && *(pattern+j)){
        if (*(text+i) == *(pattern+j)){
            j++;
            i++;
        }else if (j == 0){
            i++;
        }else{
            j = next[j-1];
        }
    }

    if (*(pattern+j) == 0){
        *pos = (int)(i-j);
        return(0);
    }else{
        *pos = -1;
        return(-1);
    }
}

//ababd***ababafgab
//00000123001